JIPS (한국정보처리학회)
Current Result Document :
| 한글제목(Korean Title) |
Combining Local and Global Features to Reduce 2-Hop Label Size of Directed Acyclic Graphs |
| 영문제목(English Title) |
Combining Local and Global Features to Reduce 2-Hop Label Size of Directed Acyclic Graphs |
| 저자(Author) |
Jinhyun Ahn
Dong-Hyuk Im
|
| 원문수록처(Citation) |
VOL 16 NO. 01 PP. 0201 ~ 0209 (2020. 02) |
한글내용
(Korean Abstract) |
|
영문내용
(English Abstract) |
The graph data structure is popular because it can intuitively represent real-world knowledge. Graph databases have attracted attention in academia and industry because they can be used to maintain graph data and allow users to mine knowledge. Mining reachability relationships between two nodes in a graph, termed reachability query processing, is an important functionality of graph databases. Online traversals, such as the breadth-first and depth-first search, are inefficient in processing reachability queries when dealing with large-scale graphs. Labeling schemes have been proposed to overcome these disadvantages. The state-of-the-art is the 2-hop labeling scheme: each node has in and out labels containing reachable node IDs as integers. Unfortunately, existing 2-hop labeling schemes generate huge 2-hop label sizes because they only consider local features, such as degrees. In this paper, we propose a more efficient 2-hop label size reduction approach. We consider the topological sort index, which is a global feature. A linear combination is suggested for utilizing both local and global features. We conduct experiments over real-world and synthetic directed acyclic graph datasets and show that the proposed approach generates smaller labels than existing approaches.
|
| 키워드(Keyword) |
Degree
Directed Acyclic Graphs
Topological Sort
2-Hop Label
|
| 파일첨부 |
PDF 다운로드
|
